package com.yww.datastructure.line.linkedlist;

import com.yww.datastructure.line.Linear;

import java.util.Iterator;
import java.util.function.Consumer;
import java.util.stream.Stream;

/**
 * @author yww
 * @description 双向链表 带哨兵
 * @since 2024/1/30 16:10
 */
public final class DoubleLinkedList<E> implements Linear<E> {
    private final Node<E> head; // 头指针
    private final Node<E> tail; // 尾指针

    public DoubleLinkedList() {
        // 初始哨兵
        head = new Node<>(null, null, null);
        tail = new Node<>(null, null, null);

        head.next = tail;
        tail.pre = head;
    }

    @Override
    public E get(int index) {
        Node<E> node = findNode(index);
        if (node == null || node == head || node == tail) {
            throw illegalIndex(index);
        }
        return node.val;
    }

    @Override
    public void addLast(E e) {
        // 找到最后一个元素
        Node<E> last = tail.pre;
        Node<E> added = new Node<>(last, e, tail);
        last.next = added;
        tail.pre = added;
    }

    @Override
    public void addFirst(E e) {
        add(e, 0);
    }

    @Override
    public void add(E e, int index) {
        // 找到前驱
        Node<E> pre = findNode(index - 1);
        if (pre == null) {
            throw illegalIndex(index);
        }
        // 找到后继
        Node<E> next = pre.next;
        Node<E> added = new Node<>(pre, e, next);
        pre.next = added;
        next.pre = added;

    }

    @Override
    public void foreach(Consumer<E> consumer) {
        Node<E> p = head.next;
        while (p != tail) {
            consumer.accept(p.val);
            p = p.next;
        }
    }

    @Override
    public Stream<E> stream() {
        Stream.Builder<E> builder = Stream.builder();
        foreach(builder::add);
        return builder.build();
    }

    public E removeLast() {
        // 待删除的最后一个节点
        Node<E> removed = tail.pre;
        // 不能删除头节点
        if (removed == head) {
            throw illegalIndex(0);
        }
        // 前驱
        Node<E> pre = removed.pre;
        pre.next = tail;
        tail.pre = pre;
        return removed.val;
    }

    @Override
    public E removeFirst() {
        return remove(0);
    }

    @Override
    public int size() {
        Node<E> p = head.next;
        int i = 0;
        while (p != tail) {
            p = p.next;
            i++;
        }
        return i;
    }

    @Override
    public E remove(int index) {
        // 找到前驱
        Node<E> pre = findNode(index - 1);
        if (pre == null) {
            throw illegalIndex(index);
        }
        // 待删除节点，不能是尾哨兵
        Node<E> removed = pre.next;
        if (removed == tail) {
            throw illegalIndex(index);
        }
        // 找到后驱
        Node<E> next = removed.next;
        pre.next = next;
        next.pre = pre;
        return removed.val;
    }

    @Override
    public boolean isEmpty() {
        return head.next == tail;
    }

    @Override
    public Iterator<E> iterator() {
        return new Iterator<E>() {
            Node<E> p = head.next;

            @Override
            public boolean hasNext() {
                return p != tail;
            }

            @Override
            public E next() {
                E res = p.val;
                p = p.next;
                return res;
            }
        };
    }

    private Node<E> findNode(int index) {
        // index == -1 时，返回头哨兵
        int i = -1;
        Node<E> p = head;
        while (p != tail) {
            if (i == index) {
                return p;
            }
            p = p.next;
            i++;
        }
        return null;
    }

    private static class Node<E> {
        Node<E> pre;
        E val;
        Node<E> next;

        // 提供构造方法，方便插入
        public Node(Node<E> pre, E val, Node<E> next) {
            this.pre = pre;
            this.val = val;
            this.next = next;
        }
    }
}
